/*
https://leetcode.cn/problems/kth-missing-positive-number/solutions/1863401/-by-lcfgrn-kh3k/
第k个缺失的正整数
类型：二分
*/
class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int i = 0, j = arr.size()-1; 
        while( i <= j ){
            int mid = i + (j - i) / 2;
            if( arr[mid] - 1 - mid < k ) i = mid + 1;
            else j = mid - 1;
        }
        return k + j + 1;
    }
};
